package linkedlist.leetcode_147_medium_sort;

public class InsertionSortList {
    /**
     * 对链表进行插入排序。
     *
     * 插入排序中的关键点在于，和当前元素的前一个元素进行比较，交换。对于数组来说可以利用下标获取，很容易
     *
     * 在链表获取前一个元素只能通过遍历的方式进行，利用几个变量进行处理。
     *
     * cur指针，表示当前待插入元素
     *
     * 利用一个哑节点dummyNode，指向head，用来插入在head节点前，且用于最后的返回。
     *
     * 利用一个pre指针来寻找待插入元素的合适位置，从dummyNode进行遍历操作。
     *
     * 利用一个lastSort指针，表示已排序部分的最后一个节点。
     */
    public ListNode insertionSortList(ListNode head) {
        //链表排序的经典base-case
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode lastSorted = head;
        ListNode cur = head.next;
        while (cur != null){
            //如果 < 待插入元素的值，说明这两个节点已经有序，继续遍历
            if(lastSorted.val <= cur.val){
                lastSorted = cur;
                cur = cur.next;
            }else { //cur的值更小，插入到合适的位置。
                ListNode pre = dummyNode;
                /*
                    寻找合适的位置
                    什么位置是合适的位置？
                        3 - 4 - 6   插入元素 = 5， 4和6之间就是合适的位置。
                 */
                while (pre.next.val <= cur.val) {
                    pre = pre.next;
                }
                /*
                    插入
                                               cur   cur.next
                        3   -   4   -   6  -   5   -   7
                                pre  lastSorted

                                        cur          cur.next
                        3   -   4   -   5  -   6   -   7
                                pre        lastSorted
                 */
                lastSorted.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;

                //下一个待插入元素
                cur = lastSorted.next;
            }
        }
        return dummyNode.next;
    }
}
